package 代码题.最近最少使用算法结构题目;

import java.util.HashMap;

/**
 * LRU数据结构每次从队列尾巴进行添加，删除队列头部
 */
public class LRUCacheMethod {
    public static void main(String[] args){
        LRUCache lruCache=new LRUCache(5);
        lruCache.put("001","用户1信息");
        lruCache.put("002","用户2信息");
        lruCache.put("003","用户3信息");
        lruCache.put("004","用户4信息");
        lruCache.put("005","用户5信息");
        System.out.println(lruCache);
        lruCache.put("004","用户2信息更新");
        lruCache.put("006","用户6信息");
        System.out.println(lruCache);
    }
}



class Node{
    Node(String key,String value){
        this.key=key;
        this.value=value;
    }
    public Node pre;
    public Node next;
    public String key;
    public String value;

    @Override
    public String toString() {
        return "Node{" +
                "key='" + key + '\'' +
                ", value='" + value + '\'' +
                '}';
    }
}

class LRUCache {
    private Node head;
    private Node end;
    private int limit;
    private HashMap<String, Node> hashMap;

    public LRUCache(int limit) {
        this.limit = limit;
        hashMap = new HashMap<String, Node>();
    }

    //添加节点，value顺带的。主要是key的比较。
    public void put(String key,String value){
        Node node=hashMap.get(key);
        if(node==null){
            //如果key不存在，插入key-value
            if(hashMap.size()>=limit){
                String oldKey=removeNode(head);
                hashMap.remove(oldKey);
            }
            node=new Node(key,value);
            addNode(node);
            hashMap.put(key,node);
        }
        else{
            //如果key存在，刷新key-value
            node.value=value;
            refreshNode(node);
        }
    }

    /**
     * 尾部插入节点
     * @param node 要插入的节点
     * */
    private void addNode(Node node){
        if(end!=null){
            end.next=node;
            node.pre=end;
            node.next=null;
        }
        end=node;
        if(head==null){
            head=node;
        }
    }

    /*
     * 刷新被访问的节点位置
     * @param node 被访问的节点
     * */
    private void refreshNode(Node node){
        //如果访问的是尾节点,即最近未被访问的节点
        if(node==end){
            return;
        }
        //移除节点
        removeNode(node);
        //重新插入节点，默认添加到尾部
        addNode((node));
    }

    /**
     * 删除Cachez中的节点
     * @param node 要删除的节点
     */
    private String removeNode(Node node) {
        if (node == end) {
            end = end.pre;
        } else if (node == head) {
            head = head.next;
        } else {
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        return node.key;
    }

    @Override
    public String toString() {
        return "LRUCache{" +
                "head=" + head +
                ", end=" + end +
                ", limit=" + limit +
                ", hashMap=" + hashMap +
                '}';
    }
}

